/* 
 * N-Queens
 */

#include "../func.h"

bool isValid(const vector<int> &C, int row, int col)
{
    for (int i = 0; i < row; ++i)
    {
        if (C[i] == col)
            return false;
        if (abs(i - row) == abs(C[i] - col))
            return false;
    }
    return true;
}
void dfs(vector<int> &C, vector<vector<string>> &result, int row)
{
    const int N = C.size();
    if (row == N)
    {
        vector<string> solution;
        for (int i = 0; i < N; ++i)
        {
            string s(N, '.');
            for (int j = 0; j < N; ++j)
            {
                if (j == C[i])
                    s[j] = 'Q';
            }
            solution.push_back(s);
        }
        result.push_back(solution);
        return;
    }

    for (int j = 0; j < N; ++j)
    {
        const bool ok = isValid(C, row, j);
        if (!ok)
            continue;
        dfs(C, result, row + 1);
    }
}

//beiwanglu